import functools


class Solution(object):
    def numMusicPlaylists(self, n, goal, k):
        base = 10 ** 9 + 7

        @functools.cache
        def dfs(i, t):
            ans = 0
            left = goal - i
            if i == goal and t == 0:
                return 1
            if left < t:
                return 0
            if t > 0:
                ans = (ans + t * dfs(i + 1, t - 1)) % base
            ans = (ans + (n - t - min(k, i)) * dfs(i + 1, t)) % base
            return ans

        return dfs(0, n)


data = Solution()
n = 2
goal = 3
k = 1
print(data.numMusicPlaylists(n, goal, k))
